/*
 * Copyright (C) 2008-2010 Oliver Horn.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.googlecode.funcj;

import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;

import com.google.common.base.Function;
import com.google.common.collect.Lists;


/**
 * Helper functions for reducing iterables. Reducing, often called folding, reduces an iterable
 * to a single value by applying a given combining function cumulatively to the elements of the
 * iterable.
 *
 * <h4>Example</h4>
 *
 * <pre>
 * List<String> list = Arrays.asList("1", "2", "3");
 * Function2<String, String, String> f = new Function2<String, String, String>() {
 *     public String apply(String arg1, String arg2) { return "(" + arg1 + " + " + arg2 + ")"; }
 * };
 *
 * Reduce.reduceLeft(list, f, "0")   // -> "(((0 + 1) + 2) + 3)"
 * Reduce.reduceLeft(list, f)        // -> "((1 + 2) + 3)"
 * Reduce.reduceRight(list, f, "0")  // -> "(1 + (2 + (3 + 0)))"
 * Reduce.reduceRight(list, f)       // -> "(1 + (2 + 3))"
 * </pre>
 *
 * @author Oliver Horn
 */
public final class Reduce {

    private Reduce() {
    }

    /**
     * Reduces the specified iterable from left to right with the given initial value.
     */
    public static final <A, B> B reduceLeft(Iterable<A> iterable, Function2<? super B, ? super A, ? extends B> function, B initial) {
        return reduceLeft(iterable.iterator(), function, initial);
    }

    /**
     * Reduces the specified iterable from left to right.
     * @throws NoSuchElementException if the input is empty
     */
    public static final <A> A reduceLeft(Iterable<A> iterable, Function2<? super A, ? super A, ? extends A> function) {
        Iterator<A> iterator = iterable.iterator();
        return reduceLeft(iterator, function, iterator.next());
    }

    private static final <A, B> B reduceLeft(Iterator<A> iterator, Function2<? super B, ? super A, ? extends B> function, B initial) {
        B result = initial;
        while (iterator.hasNext()) {
            result = function.apply(result, iterator.next());
        }
        return result;
    }

    /**
     * Reduces the specified iterable from right to left with the given initial value.
     */
    public static <A, B> B reduceRight(Iterable<A> iterable, Function2<? super A, ? super B, ? extends B> function, B initial) {
        if (iterable instanceof List) {
            return reduceRight((List<A>) iterable, function, initial);
        } else {
            return reduceRight(Lists.newArrayList(iterable), function, initial);
        }
    }

    /**
     * Reduces the specified list from right to left with the given initial value.
     */
    public static <A, B> B reduceRight(List<A> list, Function2<? super A, ? super B, ? extends B> function, B initial) {
        return reduceRight(list.listIterator(list.size()), function, initial);
    }

    /**
     * Reduces the specified iterable from right to left.
     * @throws NoSuchElementException if the input is empty
     */
    public static <A> A reduceRight(Iterable<A> iterable, Function2<? super A, ? super A, ? extends A> function) {
        if (iterable instanceof List) {
            return reduceRight((List<A>) iterable, function);
        } else {
            return reduceRight(Lists.newArrayList(iterable), function);
        }
    }

    /**
     * Reduces the specified list from right to left.
     * @throws NoSuchElementException if the input is empty
     */
    public static <A> A reduceRight(List<A> list, Function2<? super A, ? super A, ? extends A> function) {
        ListIterator<A> listIterator = list.listIterator(list.size());
        return reduceRight(listIterator, function, listIterator.previous());
    }

    private static <A, B> B reduceRight(ListIterator<A> iterator, Function2<? super A, ? super B, ? extends B> function, B initial) {
        B result = initial;
        while (iterator.hasPrevious()) {
            result = function.apply(iterator.previous(), result);
        }
        return result;
    }

    /**
     * Builds an iterable from the given seed value.
     * @return the iterable
     */
    public static <T> Iterable<T> unreduce(final Function<? super T, ? extends T> function, final T seed) {
        return new Iterable<T>() {
            public Iterator<T> iterator() {
                return new Iterator<T>() {
                    private boolean initialized = false;
                    private T value = seed;

                    public boolean hasNext() {
                        return true;
                    }

                    public T next() {
                        if (initialized) {
                            value = function.apply(value);
                        } else {
                            initialized = true;
                        }
                        return value;
                    }

                    public void remove() {
                        throw new UnsupportedOperationException();
                    }
                };
            }
        };
    }
}
